class Solution:
    def numTrees(self, n: int) -> int:
        if n==0 or n==1:
            return 1
        elif n==2:
            return n
        count=0
        for i in range(n):
            count+=self.numTrees(i)*self.numTrees(n-i-1)
        return count

'''
超时
'''

class Solution:
    def numTrees(self, n: int) -> int:
        mapper={}
        def findnum(n):
            if n==0 or n==1:
                return 1
            elif n==2:
                return n
            count=0
            for i in range(n):
                if i in mapper:
                    x=mapper[i]
                else:
                    x=findnum(i)
                    mapper[i]=x
                if n-i-1 in mapper:
                    y=mapper[n-i-1]
                else:
                    y=findnum(n-i-1)
                    mapper[n-i-1]=y
                count+=x*y
            return count
        return findnum(n)




# 执行用时：
# 40 ms
# , 在所有 Python3 提交中击败了
# 58.11%
# 的用户
# 内存消耗：
# 14.7 MB
# , 在所有 Python3 提交中击败了
# 83.39%
# 的用户